package com.lw.leetcode.arr.a;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * 1005. K 次取反后最大化的数组和
 *
 * @author liw
 * @version 1.0
 * @date 2021/12/3 11:58
 */
public class LargestSumAfterKNegations {


    public static void main(String[] args) {
        LargestSumAfterKNegations test = new LargestSumAfterKNegations();

        // 5
//        int[] arr = {4,2,3};
//        int k = 1;

        // 6
//        int[] arr = {3,-1,0,2};
//        int k = 3;

        // 13
//        int[] arr = {2,-3,-1,5,-4};
//        int k = 2;

        // 15
//        int[] arr = {-2,-3,-1,-5,-4};
//        int k = 21;

        // 13
//        int[] arr = {2,3,1,5,4};
//        int k = 21;

        // 15
        int[] arr = {2, 3, 1, 5, 4};
        int k = 20;

        int i = test.largestSumAfterKNegations(arr, k);
        System.out.println(i);

    }

    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);
        int length = nums.length;
        int sum = 0;
        int i;
        int min = Math.min(k, length);
        for (i = 0; i < min; i++) {
            if (nums[i] < 0) {
                sum -= nums[i];
            } else {
                break;
            }
        }
        for (int j = i; j < length; j++) {
            sum += nums[j];
        }
        int c = k - i;
        if (c != 0 && (c & 1) == 1) {
            if (i == 0) {
                sum -= (nums[0] << 1);
            } else if (i == length) {
                sum += (nums[length - 1] << 1);
            } else {
                sum -= (Math.min(nums[i], -nums[i - 1]) << 1);
            }
        }
        return sum;
    }

}
